"""1235. 规划兼职工作 https://leetcode.cn/problems/maximum-profit-in-job-scheduling/description/"""


from bisect import bisect_right
from typing import List


class Solution:
    # 链接：https://leetcode.cn/problems/maximum-profit-in-job-scheduling/solutions/36375/python-dong-tai-gui-hua-xiang-jie-by-jalan-2/
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        # 长度实际上都是一样的，选一个就好
        length = len(startTime)
        times = [[0, 0, 0] for _ in range(length)]
        for i in range(length):
            times[i][0] = startTime[i]
            times[i][1] = endTime[i]
            times[i][2] = profit[i]
        #  这里注意排序的方法
        times.sort()  # 按照结束时间排序

        dp = [0 for i in range(length)]

        res = 0
        s = 0
        pos = 0  # 标记位置

        for i in range(length):
            # 全部遍历容易超时
            for j in range(pos, i):
                # 区间不重合
                # 这里表示当前的起始值大于等于随后遍历其他的最大值,相当于我的开始就是你已经结束的位置并且还要向后一段所以是不重合的
                if times[i][0] >= times[j][1]:
                    # 移动 pos 的位置，每次j遍历到过去就带过去一位，表示pos前面的数已经都经过计算了，这里后面不用继续计算
                    if j == pos:
                        pos += 1
                    # s表示的是到当前j的最大收益
                    # 这里[50, 10, 90, 120]，收益会下降的原因是如果有两个工作都是与当前不重合的也就是都可以做，这里两个不同的工作收益是不一样的
                    s = max(s, dp[j])

            # 每次把当前遍历到的i给收益加上
            dp[i] = s + times[i][2]
            # 当前位置的i的收益加上以后
            res = max(res, dp[i])

        return res


# 结果：超时
class Solution:
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        # 按照结束时间排序(快速判断两个工作有没有重合)
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
        # dp[i]表示前i个工作能获得的最大利润
        dp = [0] * len(jobs)

        # 遍历每个工作
        for i in range(len(jobs)):
            # 如果当前工作是第一个工作，或者前一个工作结束后，时间不超过当前工作开始时间，则可以选择当前工作
            # 前一部获得的收益和这一步的收益比较
            dp[i] = max(dp[i - 1] if i > 0 else 0, jobs[i][2])

            # 倒序遍历，后面的大搞率满足的，这样就不用看前面的一些不满足条件的
            for j in range(i - 1, -1, -1):
                # /如果前一个工作的结束时间不超过当前工作的开始时间，则可以选择当前工作
                if jobs[j][1] <= jobs[i][0]:
                    # 更新dp[i]的值，取 当前工作前最大收益 和前一个工作收益最大加上当前工作的收益  的最大值
                    dp[i] = max(dp[i], dp[j] + jobs[i][2])
                    break

        # 返回前n个工作能获得的最大利润
        return dp[-1]


# 功能性描述：在上面的基础上优化，搜索采用二分查找
class Solution:
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        # 按照结束时间排序
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])

        # 初始化dp数组
        dp = [0] * len(jobs)
        # 初始化endTime数组用于二分查找
        end_times = [job[1] for job in jobs]

        # 遍历每个工作
        for i in range(len(jobs)):
            # 当前工作的利润
            current_profit = jobs[i][2]

            # 找到不重叠的前一个工作
            # 这个函数是在列表中找到一个合适的插入点，以保持列表的有序性，要-1是因为函数从1开始的
            # 找到endTime小于等于当前startTime的位置
            j = bisect_right(end_times, jobs[i][0]) - 1

            # 如果找到这样的工作，更新dp[i]
            # if j != -1:
            current_profit += dp[j]

            # 更新dp[i]为当前工作的最大利润或者不选择当前工作的最大利润
            dp[i] = max(dp[i - 1] if i > 0 else 0, current_profit)

        # 返回最后一个位置的最大利润
        return dp[-1]


# startTime = [1, 2, 3, 3]
# endTime = [3, 4, 5, 6]
# profit = [50, 10, 40, 70]
# test = Solution()
# print(test.jobScheduling(startTime, endTime, profit))
